English Version

动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。

enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。

dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。

示例1:

 输入： ["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"] [[], [[0, 0]], [[1, 0]], [], [], []]  输出： [null,null,null,[0,0],[-1,-1],[1,0]] 

示例2:

 输入： ["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"] [[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]  输出： [null,null,null,null,[2,1],[0,0],[1,0]] 

说明:

1. 收纳所的最大容量为20000

我们定义一个长度为 $2$ 的数组 $q$，用于存放猫和狗的队列。

在 enqueue 操作中，假设动物编号为 $i$，动物种类为 $j$，我们将 $i$ 入队到 $q[j]$ 中。

在 dequeueAny 操作中，我们判断 $q[0]$ 是否为空，或者 $q[1]$ 不为空且 $q[1][0] < q[0][0]$，如果是，则调用 dequeueDog，否则调用 dequeueCat。

在 dequeueDog 操作中，如果 $q[1]$ 为空，则返回 $[-1, -1]$，否则返回 $[q[1].pop(), 1]$。

在 dequeueCat 操作中，如果 $q[0]$ 为空，则返回 $[-1, -1]$，否则返回 $[q[0].pop(), 0]$。

以上操作的时间复杂度均为 $O(1)$，空间复杂度为 $O(n)$，其中 $n$ 为动物收容所中动物的数量。

classAnimalShelf: def__init__(self): self.q= [deque(), deque()] defenqueue(self, animal: List[int]) ->None: i, j=animalself.q[j].append(i) defdequeueAny(self) ->List[int]: ifnotself.q[0] or (self.q[1] andself.q[1][0] <self.q[0][0]): returnself.dequeueDog() returnself.dequeueCat() defdequeueDog(self) ->List[int]: return [-1, -1] ifnotself.q[1] else [self.q[1].popleft(), 1] defdequeueCat(self) ->List[int]: return [-1, -1] ifnotself.q[0] else [self.q[0].popleft(), 0] # Your AnimalShelf object will be instantiated and called as such:# obj = AnimalShelf()# obj.enqueue(animal)# param_2 = obj.dequeueAny()# param_3 = obj.dequeueDog()# param_4 = obj.dequeueCat()

classAnimalShelf { privateDeque<Integer>[] q = newDeque[2]; publicAnimalShelf() { Arrays.setAll(q, k -> newArrayDeque<>()); } publicvoidenqueue(int[] animal) { q[animal[1]].offer(animal[0]); } publicint[] dequeueAny() { if (q[0].isEmpty() || (!q[1].isEmpty() && q[1].peek() < q[0].peek())) { returndequeueDog(); } returndequeueCat(); } publicint[] dequeueDog() { returnq[1].isEmpty() ? newint[] {-1, -1} : newint[] {q[1].poll(), 1}; } publicint[] dequeueCat() { returnq[0].isEmpty() ? newint[] {-1, -1} : newint[] {q[0].poll(), 0}; } } /** * Your AnimalShelf object will be instantiated and called as such: * AnimalShelf obj = new AnimalShelf(); * obj.enqueue(animal); * int[] param_2 = obj.dequeueAny(); * int[] param_3 = obj.dequeueDog(); * int[] param_4 = obj.dequeueCat(); */

classAnimalShelf { public:AnimalShelf() { } voidenqueue(vector<int> animal) { q[animal[1]].push(animal[0]); } vector<int> dequeueAny() { if (q[0].empty() || (!q[1].empty() && q[1].front() < q[0].front())) { returndequeueDog(); } returndequeueCat(); } vector<int> dequeueDog() { if (q[1].empty()) { return {-1, -1}; } int dog = q[1].front(); q[1].pop(); return {dog, 1}; } vector<int> dequeueCat() { if (q[0].empty()) { return {-1, -1}; } int cat = q[0].front(); q[0].pop(); return {cat, 0}; } private: queue<int> q[2]; }; /** * Your AnimalShelf object will be instantiated and called as such: * AnimalShelf* obj = new AnimalShelf(); * obj->enqueue(animal); * vector<int> param_2 = obj->dequeueAny(); * vector<int> param_3 = obj->dequeueDog(); * vector<int> param_4 = obj->dequeueCat();*/

typeAnimalShelfstruct { q [2][]int } funcConstructor() AnimalShelf { returnAnimalShelf{} } func (this*AnimalShelf) Enqueue(animal []int) { this.q[animal[1]] =append(this.q[animal[1]], animal[0]) } func (this*AnimalShelf) DequeueAny() []int { iflen(this.q[0]) ==0|| (len(this.q[1]) >0&&this.q[0][0] >this.q[1][0]) { returnthis.DequeueDog() } returnthis.DequeueCat() } func (this*AnimalShelf) DequeueDog() []int { iflen(this.q[1]) ==0 { return []int{-1, -1} } dog:=this.q[1][0] this.q[1] =this.q[1][1:] return []int{dog, 1} } func (this*AnimalShelf) DequeueCat() []int { iflen(this.q[0]) ==0 { return []int{-1, -1} } cat:=this.q[0][0] this.q[0] =this.q[0][1:] return []int{cat, 0} } /** * Your AnimalShelf object will be instantiated and called as such: * obj := Constructor(); * obj.Enqueue(animal); * param_2 := obj.DequeueAny(); * param_3 := obj.DequeueDog(); * param_4 := obj.DequeueCat(); */

classAnimalShelf{privateq: number[][]=[[],[]];constructor(){}enqueue(animal: number[]): void{const[i,j]=animal;this.q[j].push(i);}dequeueAny(): number[]{if(this.q[0].length===0||(this.q[1].length>0&&this.q[0][0]>this.q[1][0])){returnthis.dequeueDog();}returnthis.dequeueCat();}dequeueDog(): number[]{if(this.q[1].length===0){return[-1,-1];}return[this.q[1].shift()!,1];}dequeueCat(): number[]{if(this.q[0].length===0){return[-1,-1];}return[this.q[0].shift()!,0];}}/** * Your AnimalShelf object will be instantiated and called as such: * var obj = new AnimalShelf() * obj.enqueue(animal) * var param_2 = obj.dequeueAny() * var param_3 = obj.dequeueDog() * var param_4 = obj.dequeueCat() */

use std::collections::VecDeque;structAnimalShelf{q:[VecDeque<i32>;2],}implAnimalShelf{fnnew() -> Self{AnimalShelf{q:[VecDeque::new(),VecDeque::new()],}}fnenqueue(&mutself,animal:Vec<i32>){self.q[animal[1]asusize].push_back(animal[0]);}fndequeue_any(&mutself) -> Vec<i32>{ifself.q[0].is_empty() || (!self.q[1].is_empty() && self.q[1].front().unwrap() < self.q[0].front().unwrap()){self.dequeue_dog()}else{self.dequeue_cat()}}fndequeue_dog(&mutself) -> Vec<i32>{ifself.q[1].is_empty(){vec![-1, -1]}else{let dog = self.q[1].pop_front().unwrap();vec![dog,1]}}fndequeue_cat(&mutself) -> Vec<i32>{ifself.q[0].is_empty(){vec![-1, -1]}else{let cat = self.q[0].pop_front().unwrap();vec![cat,0]}}}

classAnimalShelf{privatevarq:[[Int]]=Array(repeating:[], count:2)init(){}func enqueue(_ animal:[Int]){q[animal[1]].append(animal[0])}func dequeueAny()->[Int]{ifq[0].isEmpty || (!q[1].isEmpty && q[1].first! <q[0].first!){returndequeueDog()}returndequeueCat()}func dequeueDog()->[Int]{returnq[1].isEmpty ?[-1,-1]:[q[1].removeFirst(),1]}func dequeueCat()->[Int]{returnq[0].isEmpty ?[-1,-1]:[q[0].removeFirst(),0]}} /** * Your AnimalShelf object will be instantiated and called as such: * let obj = new AnimalShelf(); * obj.enqueue(animal); * let param_2 = obj.dequeueAny(); * let param_3 = obj.dequeueDog(); * let param_4 = obj.dequeueCat(); */